1. Field of the Invention
The present invention pertains to the field of compiling source code into executable code in computer systems. More particularly, this invention relates to software pipelining of nested loops.
2. Background of the Related Art
Generally, a compiler is a computer program that compiles or translates a computer program written in source code by a programmer into code that can be executed by a processor. Source code typically includes numerous loops, which are sections of code that may be executed more than once in succession. Many computer programs spend the majority of their execution time in loops. Among the many techniques for improving the execution time of computer programs is increasing the amount of instruction level parallelism that can be used by today's advanced processors.
One technique for increasing instruction level parallelism is software pipelining. Software pipelining is a method that restructures loops so that instructions from various iterations of the loop are executed at the same time.
FIG. 1a shows a scalar schedule of a simple loop consisting of operations A, B, and C. In the scalar schedule 110 each operation is scheduled to be executed one after the other. In the example shown in FIG. 1a each operation is assumed to require one cycle to execute. The operations A, B, and C from the first iteration are labeled A1, B1, and C1, the operations from the second iteration of the loop are labeled A2, B2, and C2, etc. FIG. 1a shows that the scalar schedule 110 requires fifteen cycles to complete.
FIG. 1b shows a software pipeline schedule of the same simple loop described in connection with FIG. 1a, above. In the software pipeline schedule 120, operations from different iterations of the loop are scheduled to be executed during the same cycle. In this example, the software pipeline schedule 120 requires 7 cycles to execute. Thus, a large improvement in execution time is achieved in this example by software pipelining the loop.
Computer programs typically do not consist of only a single loop, or multiple loops at the same level within a hierarchy. Rather, computer programs can include loops within loops (also referred to as nested loops) such that there are loops at numerous levels within a hierarchy. Typical processors/compilers allocate a single storage area for each function or procedure in the executable code regardless of whether that function or procedure contains nested loops.
FIG. 2a illustrates an example of nested loops (an outer loop 210 and an inner loop 215) within a procedure or function written in source code that will be compiled to execute using a single storage area 220. Since a single storage area is allocated, if two or more software pipelined loops from different levels in a loop hierarchy, for example the inner loop 215 and the outer loop 210, are allowed to be active at a given moment in time, the execution of instructions included in the inner loop could overwrite storage locations used for execution of instructions included in the outer loop. As a result, prior methods for software pipelining are not able to pipeline nested loops efficiently, but typically pipeline the innermost loop(s) (i.e., the loop(s) at the lowest level of the hierarchy) and schedule the outer loops in a scalar fashion.
Computer programs spend significant execution time in other than the innermost loops, and as a result, pipelining only the innermost loops limits the amount of execution time improvement that can be achieved through prior software pipelining techniques. Therefore, a method for software pipelining nested loops is desirable.